package com.cjm.algorithm.queue;

import java.util.*;

public class Ti347 {
    public static void main(String[] args) {
        Ti347 ti347 = new Ti347();
        int[] ints = ti347.topKFrequent(new int[]{1, 1, 1, 2, 2, 3}, 2);
        System.err.println("OK");
    }

    public int[] topKFrequent(int[] nums, int k) {
        PriorityQueue<Ti347Help> deque = new PriorityQueue<>(k, new Comparator<Ti347Help>() {
            @Override
            public int compare(Ti347Help o1, Ti347Help o2) {
                return o1.getCount() - o2.getCount();
            }
        });
        Map<Integer, Ti347Help> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int item = nums[i];
            Ti347Help ti347Help = map.get(item);
            if (ti347Help == null) {
                ti347Help = new Ti347Help(item, 1);
                map.put(item, ti347Help);
            } else {
                ti347Help.setCount(ti347Help.getCount() + 1);
            }
        }


        Set<Map.Entry<Integer, Ti347Help>> entries = map.entrySet();
        entries.forEach(item -> {
            Ti347Help next = item.getValue();
            if (deque.size() == k) {
                if (deque.peek().getCount() < next.getCount()) {
                    deque.poll();
                    deque.offer(next);
                }
            } else {
                deque.add(next);
            }
        });

        int[] res = new int[k];
        for (int i = k - 1; i>=0; i--) {
            res[i] = deque.poll().getValue();
        }

        return res;
    }

    class Ti347Help {
        private Integer value;
        private Integer count;

        public Ti347Help(Integer value, Integer count) {
            this.value = value;
            this.count = count;
        }

        public Integer getValue() {
            return value;
        }

        public void setValue(Integer value) {
            this.value = value;
        }

        public Integer getCount() {
            return count;
        }

        public void setCount(Integer count) {
            this.count = count;
        }
    }
}
